#include<iostream>
#include<stack>

using namespace std;

struct BinaryTreeNode {
	int value;
	BinaryTreeNode * left;
	BinaryTreeNode * right;
};

BinaryTreeNode * CreateBinaryTreeNode(int value){
    BinaryTreeNode * pHead = new BinaryTreeNode();
    pHead->value = value;
    pHead -> left = pHead -> right = nullptr;
    return pHead;
}

// connect ListNode
void ConnectTreeNodes( BinaryTreeNode * root , 
					BinaryTreeNode * left, BinaryTreeNode * right){
    root -> left = left;
	root -> right = right;
}


bool isSymmetricalBinaryTreeRecursive(BinaryTreeNode * root1, BinaryTreeNode * root2){
    if ( root1 == nullptr && root2 == nullptr )
        return true;
    if ( root1 == nullptr || root2 == nullptr )
        return false;
    if ( root1 -> value == root2 -> value ){
        return isSymmetricalBinaryTreeRecursive(root1->left, root2->right) 
            && isSymmetricalBinaryTreeRecursive(root1->right, root2->left);
    }
    return false;

}

// 递归实现
bool isSymmetricalBinaryTreeRecursive(BinaryTreeNode * root){
	if ( root == nullptr )
		return false;
    return isSymmetricalBinaryTreeRecursive(root, root);
}


// 循环实现
bool symmetricalBinaryTreeLoop(BinaryTreeNode * root){
	
}

void printTreeNode(BinaryTreeNode * root){
	if ( root != nullptr ){
		cout << root -> value << endl;
		printTreeNode(root->left);
		printTreeNode(root->right);
	}
}

int main(void){
	BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8);
    BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6);
    BinaryTreeNode* pNode10 = CreateBinaryTreeNode(6);
    BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
    BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7);
    BinaryTreeNode* pNode9 = CreateBinaryTreeNode(9);
    BinaryTreeNode* pNode11 = CreateBinaryTreeNode(11);

	// Test 1
    ConnectTreeNodes(pNode8, pNode6, pNode10);
    ConnectTreeNodes(pNode6, pNode5, pNode7);
    ConnectTreeNodes(pNode10, pNode7, pNode5);

    // Test 2
    ConnectTreeNodes(pNode8, pNode6, pNode10);
    ConnectTreeNodes(pNode6, pNode5, pNode7);
    ConnectTreeNodes(pNode10, pNode7, pNode11);
    
    // Test 3
    ConnectTreeNodes(pNode8, pNode6, pNode10);
    ConnectTreeNodes(pNode6, pNode5, pNode7);
    ConnectTreeNodes(pNode10, pNode7, nullptr);

    cout << "result: " << isSymmetricalBinaryTreeRecursive(nullptr) << endl;
	return 0;
}